package third

/*
	把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
	你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

	示例 1:
	输入: 1
	输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

	示例2:
	输入: 2
	输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

	限制：
	1 <= n <= 11

	通过次数69,821提交次数123,796

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

func DicesProbability(n int) []float64 {
	return dicesProbability(n)
}

/*
	f(i,x)表示i个骰子朝上一面点数和为x的概率
	f(i,x) = sum(f(i-1,x-1),f(i-1,x-2),f(i-1,x-3)...)
*/
func dicesProbability(n int) []float64 {
	dp := make([][]float64, n+1)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]float64, n*6+1)
	}
	for x := 1; x <= 6; x++ {
		dp[1][x] = 1.0 / 6.0
	}
	for i := 2; i <= n; i++ {
		for x := i; x <= 6*i; x++ {
			for k := 1; k <= 6; k++ {
				if x > k {
					dp[i][x] += dp[i-1][x-k] * 1.0 / 6.0
				}
			}
		}
	}
	return dp[len(dp)-1][n:]
}